//
// Description: 筛素数 模板
// Created by Loading on 2021/8/17.
//

#include <bits/stdc++.h>

using namespace std;

// 数据范围
constexpr int N = 1e6;
// 标记数组 prime[i] = true 表示 i 是素数，反之为合数
bool prime[N + 1];

/* 埃拉托斯特尼(Eratosthenes)法 筛素数，时间复杂度：O(nlog(logn)) */
vector<int> Eratosthenes_Prime(int n) {
    // 将标记数组全部初始化为 true，素数
    memset(prime, true, sizeof prime);

    prime[0] = prime[1] = false;
    vector<int> res;
    for (int i = 2; i <= n; i++) {
        if (!prime[i]) {
            // i 为合数
            continue;
        } else {
            // 素数加入结果集
            res.emplace_back(i);
        }
        for (int j = i * 2; j <= n; j += i) {
            // 将 i 的倍数标记为合数
            prime[j] = false;
        }
    }
    return res;
}

/* 线性筛素数，时间复杂度：O(n) */
/* 核心原理：对于每个合数，都只由它最小的质因子筛掉 */
vector<int> Linear_Prime(int n) {
    // 将标记数组全部初始化为 true，素数
    memset(prime, true, sizeof prime);

    prime[0] = prime[1] = false;
    vector<int> res;
    for (int i = 2; i <= n; ++i) {
        // 素数加入结果集，当prime[i] = true时，说明没有被前面的任何一个素数筛掉，所以 i 为素数
        if (prime[i]) {
            res.emplace_back(i);
        }
        // 筛掉素数表中 从 i 的倍数开始的合数，要注意不要重复筛除
        /*
         * j < res.size() 条件也可以省略，因为没有等到 j 的越界，循环已经结束；
         * 因为：i 为素数时，res[j] == i 时，循环会break；i 为合数时，res[j] 为 i 的最小质因子时，循环同样会break。
         * 另外，res[j] <= n / i 条件不推荐写成 res[j] * i <= n，可能会有越界风险
         */
        for (int j = 0; j < res.size() && res[j] <= n / i; ++j) {
            prime[i * res[j]] = false;
            /* 关键代码 */
            /* 防止筛掉重复的合数，例如：i = 2 的时候，仅筛掉 4 即可，因为 6 可以由 i = 3 时筛掉 */
            if (i % res[j] == 0) {
                break;
            }
        }
    }
    return res;
}

int main() {
    int n = 100;
    // 埃氏筛
    vector<int> res = Eratosthenes_Prime(n);
    for (auto &x : res) {
        cout << x << " ";
    }
    cout << endl;

    // 线性筛
    res = Linear_Prime(n);
    for (auto &x : res) {
        cout << x << " ";
    }
    cout << endl;
}